package top.ivansong92.example.leetcode.learning.data.struct.collection;


import org.junit.Test;

import java.util.Set;
import java.util.*;
import java.util.concurrent.atomic.AtomicInteger;
import java.util.stream.Collectors;

public class TestExample3 {


    @Test
    public void testLemonadeChange() {
    }

    public List<List<String>> groupAnagrams(String[] strs) {
        if (strs == null || strs.length == 0) {
            return Collections.emptyList();
        }
        int len = strs.length;
        if (len == 1) {
            return Collections.singletonList(Collections.singletonList(strs[0]));
        }

        Map<String, List<String>> groupMap = new HashMap<>();
        for (int i = 0; i < len; i++) {
            char[] chars = strs[i].toCharArray();
            Arrays.sort(chars);
            String key = new String(chars);
            List<String> list = groupMap.computeIfAbsent(key, l -> new ArrayList<>());
            list.add(strs[i]);
        }
        return new ArrayList<>(groupMap.values());
    }


    /**
     * 149. 直线上最多的点数
     * @param points
     * @return
     */
    public int maxPoints(int[][] points) {
        if (points == null || points.length == 0) {
            return 0;
        }

        int len = points.length;
        if (len < 3) {
            return len;
        }

        int res = 0;
        for (int i = 0; i <= len - 3; i++) {
            int x = points[i][0];
            int y = points[i][1];
            for (int j = i + 1; j <= len - 2; j++) {
                int x1 = points[j][0];
                int y1 = points[j][1];
                int counter = 2;
                for (int k = j + 1; k <= len - 1; k++) {
                    int x2 = points[k][0];
                    int y2 = points[k][1];
                    if ((x - x1) * (y - y2) == (x - x2) * (y - y1)) {
                        counter++;
                    }
                }
                res = Math.max(res, counter);
            }
        }
        return res;
    }

    public int numberOfBoomerangs(int[][] points) {
        if (points == null || points.length < 3) {
            return 0;
        }
        int len = points.length;
        int res = 0;
        Map<Integer, AtomicInteger> distanceMap = new HashMap<>();
        for (int i = 0; i <= len - 1; i++) {
            int[] point1 = points[i];
            for (int j = 0; j <= len - 1; j++) {
                if (i == j) {
                    continue;
                }
                int distance = getDistance(point1, points[j]);
                distanceMap.computeIfAbsent(distance, e -> new AtomicInteger(0)).incrementAndGet();
            }
            for (AtomicInteger counter : distanceMap.values()) {
                int val = counter.get();
                if (val > 1) {
                    res += val * (val - 1);
                }
            }
            distanceMap.clear();
        }
        return res;
    }

    private int getDistance(int[] point1, int[] point2) {
        int x = point1[0] - point2[0], y = point1[1] - point2[1];
        return x * x + y * y;
    }

    public int[] intersect(int[] nums1, int[] nums2) {
        if (nums1 == null || nums1.length == 0 || nums2 == null || nums2.length == 0) {
            return new int[0];
        }
        Map<Integer, AtomicInteger> nums1Counter = new HashMap<>();
        for (int num : nums1) {
            nums1Counter.computeIfAbsent(num, e -> new AtomicInteger(0)).incrementAndGet();
        }

        List<Integer> res = new ArrayList<>();
        for (int num : nums2) {
            AtomicInteger counter = nums1Counter.get(num);
            if (counter == null || counter.decrementAndGet() < 0) {
                continue;
            }
            res.add(num);
        }
        return res.stream().mapToInt(Integer::intValue).toArray();
    }

    public boolean isAnagram(String s, String t) {
        if (s == null || t == null || s.length() != t.length()) {
            return false;
        }

        Map<Character, AtomicInteger> map = new HashMap<>();
        char[] chars = s.toCharArray();
        for (char ch : chars) {
            map.computeIfAbsent(ch, e -> new AtomicInteger(0)).incrementAndGet();
        }

        char[] chars1 = t.toCharArray();

        for (char ch : chars1) {
            AtomicInteger val = map.get(ch);
            if (val == null || val.decrementAndGet() < 0) {
                return false;
            }
        }
        for (AtomicInteger val : map.values()) {
            if (val.get() != 0) {
                return false;
            }
        }
        return true;
    }


    public int rob(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }

        int len = nums.length;
        if (len == 1) {
            return nums[0];
        } else if (len == 2) {
            return Math.max(nums[0], nums[1]);
        } else if (len == 3) {
            return Math.max(nums[2], Math.max(nums[0], nums[1]));
        }

        int[] dp1 = new int[len - 1];
        int[] dp2 = new int[len - 1];
        dp1[0] = nums[0];
        dp1[1] = Math.max(nums[0], nums[1]);
        dp2[0] = nums[1];
        dp2[1] = Math.max(nums[2], nums[1]);
        for (int i = 2; i < len - 1; i++) {
            dp1[i] = Math.max(dp1[i - 1], nums[i] + dp1[i - 2]);
            dp2[i] = Math.max(dp2[i - 1], nums[i + 1] + dp2[i - 2]);
        }
        return Math.max(dp1[len - 2], dp2[len - 2]);
    }





}
